There has been proposed a technique of detecting an instruction sequence matching a predetermined pattern from a program to be optimized and replacing the instruction sequence with another instruction sequence determined in advance in accordance with the pattern. This technique can optimize a program, for example, by replacing a sequence of instructions for performing a certain kind of processing with a single instruction producing the same processing result as the processing performed by the sequence of instructions. The instruction which replaces the sequence of instructions is, for example, a TRT instruction in the S/390 architecture provided by IBM Corporation.
The following are documents are referred to and/or considered with respect to an embodiment:                [Non-Patent Document 1]        Jianghai Fu. Directed graph pattern matching and topological embedding. Journal of Algorithms, 22(2):372-391, February 1997.        [Non-Patent Document 2]        S. S. Muchnick. Advanced compiler design and implementation,        Morgan Kaufmann Publishers, Inc., 1997.        [Non-Patent Document 3]        Arvind Gupta and Naomi Nishimura. Finding Largest Subtrees and Smallest Supertrees, Algorithmica, Vol. 21, No. 2, pp. 183-210, 1998        [Non-Patent Document 4]        http://publibz.boulder.ibm.com/epubs/pdf/dz9zr002.pdf, pp. 7-180        
A TRT instruction is an instruction to scan a predetermined storage area in order from the top and output an address or the like at which a value satisfying a predetermined condition is stored (see Non-Patent Document 4). FIG. 16 is a control flow graph corresponding to processing according to a TRT instruction. The processing by means of the TRT instruction corresponds to a sequence of processing steps by which values stored in a storage area byte array are read out in order from the top of the storage area to a variable ch, and which ends when one of conditions cond1 to condN is satisfied. A compiler may replace such a processing sequence with a single TRT instruction to optimize a program.
Disclosure of the invention and problems solved by the invention:                However, it is rare that a program to be optimized completely matches a predetermined pattern. If such a match does not occur, optimization is abandoned in the conventional art. Therefore there has been a possibility of failure to effectively utilize an instruction such as a TRT instruction specific to an architecture.        It is, therefore, an object of the present invention to provide a compiler, an optimization method, a compiler program, and a recording medium as a solution to the above-described problem. This object can be attained by a combination of features described in the independent claims in the appended claims. In the dependent claims, further advantageous examples of the present invention are specified.        